/*
 * @Author: liusheng
 * @Date: 2022-03-28 09:56:01
 * @LastEditors: liusheng
 * @LastEditTime: 2022-06-26 19:52:23
 * @Description: 剑指 Offer II 001. 整数除法
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 * 剑指 Offer II 001. 整数除法
给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。

 

注意：

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231−1]。本题中，如果除法结果溢出，则返回 231 − 1
 

示例 1：

输入：a = 15, b = 2
输出：7
解释：15/2 = truncate(7.5) = 7
示例 2：

输入：a = 7, b = -3
输出：-2
解释：7/-3 = truncate(-2.33333..) = -2
示例 3：

输入：a = 0, b = 1
输出：0
示例 4：

输入：a = 1, b = 1
输出：1
 

提示:

-231 <= a, b <= 231 - 1
b != 0
 

注意：本题与主站 29 题相同：https://leetcode-cn.com/problems/divide-two-integers/

 

通过次数39,199  提交次数184,471
 */

#include "header.h"
using namespace std;
class Solution {
public:
    int divide(int dividend, int divisor) {
        int intMax = (0x7f << 24) + (0xff << 16) + (0xff << 8) + 0xff;
        if(divisor == 0)
        {
            return intMax;
        }

        if(divisor == (0x1 << 31))
        {
            if(dividend == divisor)
            {
                return 1;
            }

            return 0;
        }

        //convert to positive
        int dividend_sign = (dividend >> 31) & 0x1;
        int divisor_sign = (divisor >> 31) & 0x1;
        bool negative = dividend_sign ^ divisor_sign;
        int offset = 0;
        if(dividend == (0x1 << 31))
        {
            if(divisor == -1)
            {
                return intMax;
            }
            else if(divisor == 1)
            {
                return (0x1 << 31);
            }
            else 
            {
                if(negative)
                {
                    offset = -1;
                    dividend += divisor;
                }
                else
                {
                    offset = 1;
                    dividend -= divisor;
                }
            }
            
        }


        int positive_dividend = abs(dividend);
        int positive_divisor = abs(divisor);
        

        int result = 0;
        for(int i = 31; i >= 0; --i )
        {
            // divisor * 2^i <= dividend
            if((positive_dividend >> i) >= positive_divisor )
            {
                result += 0x1 << i;
                positive_dividend -=  positive_divisor << i;
            }       
        }

        result = negative ?  -result : result;
        return result + offset;
    }
};

class Solution {
public:
    int divide(int a, int b) {
        int offset = 0;
        bool sign = !(((a >> 31) & 1) ^ ((b >> 31) & 1));

        if (b == INT_MIN)
        {
            if (a == b)
            {
                return 1;
            }

            return 0;
        }

        if (a == INT_MIN)
        {
            //overflow
            if (b == -1)
            {
                return INT_MAX;
            }
            else if (b == 1)
            {
                return INT_MIN;
            }
            else
            {
                if (sign)
                {
                    offset = 1;
                    a -= b;
                }
                else
                {
                    offset = -1;
                    a += b;
                }
            }
        }

        a = abs(a);
        b = abs(b);
        
        int result = 0;
        for (int i = 31; i >= 0; --i)
        {
            if ((a >> i) >= b)
            {
                result += 1 << i;
                a -= b * (1 << i);
            }
        }
        return sign ? result + offset : -result + offset;
    }
};